package cn.walls1717.leetcode.list;

/**
 * 203. 移除链表元素
 * 力扣地址：https://leetcode.cn/problems/remove-linked-list-elements/
 *
 * @author walls1717
 * @since 2022/5/14
 **/
public class T203 {

    /**
     * 不设置新的头节点，在原链表上操作
     *
     * @param head 链表
     * @param val  值
     * @return 新链表
     */
    public ListNode removeElements(ListNode head, int val) {
        // 当要移除的元素为头节点时，将头节点设置为头节点下一个元素
        while (head != null && head.val == val) {
            head = head.next;
        }
        // 如果给的链表为空，那么直接返回这个空链表
        if (head == null) {
            return null;
        }

        // 当前节点
        ListNode pre = head;
        // 当前节点的下一个节点
        ListNode cur = head.next;

        // 当当前节点的下一个节点为空，证明已经循环完整个链表
        while (cur != null) {
            /*
             前面已经对头节点进行过判断，所以这里头节点肯定不会是要移除的元素。
             因此直接判断，头节点的下一个节点是否是要移除的元素，
             如果是要移除的元素，将当前节点的下一个节点指针指向，下一个节点的下一个节点，
             也就是说将当前节点的下一个节点，要删除元素的下一个节点。
             */
            if (cur.val == val) {
                pre.next = cur.next;
            } else {
                // 如果不需要删除，移动当前节点的位置
                pre = cur;
            }
            // 移动当前节点下一个节点的位置
            cur = cur.next;
        }
        return head;
    }

    /**
     * 设置新的头节点
     *
     * @param head 链表
     * @param val  值
     * @return 新链表
     */
    public ListNode removeElements2(ListNode head, int val) {
        // 如果链表为空，直接返回空
        if (head == null) {
            return null;
        }
        // 设置新的头节点，防止出现需要删除头节点的情况
        ListNode newHead = new ListNode(-1, head);
        ListNode pre = newHead;
        ListNode cur = newHead.next;

        while (cur != null) {
            if (cur.val == val) {
                pre.next = cur.next;
            } else {
                pre = cur;
            }
            cur = cur.next;
        }
        /*
         这里因为设置了新的头节点，所以在输出的时候，
         新的头节点的下一个节点作为头节点才是要输出的正确结果
         */
        return newHead.next;
    }

}
